package 中等.动态规划.其他;

/**
 * 假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜
 * 色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
 * 当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成
 * 本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
 * 例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 
 * 表示第 1 号房子粉刷成绿色的花费，以此类推。
 * <p>
 * 请计算出粉刷完所有房子最少的花费成本。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/JEj789
 */
public class 粉刷房子_offer091 {

    public static void main(String[] args) {

        int[][] costs = {{5, 8, 6}, {19, 14, 13}, {7, 5, 12}, {14, 15, 17}, {3, 20, 10}};
        System.out.println(new 粉刷房子_offer091().minCost1(costs));

    }

    /**
     * 动态规划
     * 子问题:
     * 刷完第 [0,n] 个房子花费的最少成本是多少
     * 思路:
     * 需要保存在 [0,n-1] 个房子中，选择第 n-1 个房子的三种颜色，
     * 分别需要最少的花费是多少
     * <p>
     * 空间优化:
     * 因为第 n 个房子的颜色只和第 n-1 个房子的颜色有关，
     * dp[i] 表示 选择第 i 个颜色的花费最少花费是多少
     *
     * @param costs
     * @return
     */
    public int minCost1(int[][] costs) {
        int[] dp = new int[3];
        for (int i = 0; i < 3; i++) {
            dp[i] = costs[0][i];
        }
        for (int house = 1; house < costs.length; house++) {
            // 需要临时存储上一个房子选择某个颜色时的总花费，不然下面的结果不正确
            int pre0Sum = dp[0], pre1Sum = dp[1], pre2Sum = dp[2];
            // 当前房子选择第 0 个颜色时，上一个房子只能选择第 1 , 2 个颜色！！！
            dp[0] = Math.min(pre1Sum + costs[house][0], pre2Sum + costs[house][0]);
            dp[1] = Math.min(pre0Sum + costs[house][1], pre2Sum + costs[house][1]);
            dp[2] = Math.min(pre0Sum + costs[house][2], pre1Sum + costs[house][2]);
        }
        return Math.min(dp[2], Math.min(dp[0], dp[1]));
    }

    private int min = Integer.MAX_VALUE;

    /**
     * 深度搜索查找每一种情况
     *
     * @param costs
     * @return
     */
    public int minCost(int[][] costs) {
        for (int column = 0; column < costs[0].length; column++) {
            dfs(0, column, costs, 0);
        }
        return min;
    }

    public void dfs(int row, int column, int[][] costs, int sum) {
        sum += costs[row][column];
        if (sum > min) return;
        if (row == costs.length - 1) {
            min = Math.min(min, sum);
            return;
        }
        for (int nextCol = 0; nextCol < costs[0].length; nextCol++) {
            if (column == nextCol) continue;
            dfs(row + 1, nextCol, costs, sum);
        }
    }

}
